
package toster;
import java.util.ArrayList;

/**
 * This class is a bunch of static helper methods
 * @author zach
 */
//TODO make sure not to break things
public class Function {
    public static final int filled =2;
    public static final int empty=-2;

    /**
     *
     * @param in, array you want to check the number of permutations
     * @param size, length of the array
     * @return number of permutations
     */
    public static long perms(int[] in,int size){
        int ones=in.length;
        int zeros=size-ones-sum(in);
        return bang(ones+zeros)/(bang(zeros)*bang(ones));
    }

    /**
     * @param in
     * @return the factorial of in
     * the ! in standard notation
     */
    public static long bang(int in){
        long out =1;
        for(long i=1;i<in;i++)
            out*=i;
        return out;
    }
    /**
     * @return the sum of every int in an array
     * @param in
     */
    public static int sum(int[] in){
        int out=0;
        for(int i:in)
            out+=i;
        return out;
    }

    /**
     * Makes all permutation of the array you give it
     * @return makes the powers set of nums
     * @param nums array you want to get permutation of
     */
    public static int[][] PowerSet(int[] nums) {
        int[][] out=new int[nums.length*nums.length][nums.length*nums.length];
        for (int i = 0; i < out.length; i++) {
            out[i][0] = nums[i / nums.length];
            ArrayList<Integer> lain = new ArrayList<Integer>();

            for (int yyz : nums) {
                if (yyz != nums[i / nums.length]) {
                    lain.add(yyz);
                }
            }

            for (int q = 1; q < out[i].length; q++) {
                out[i][q] = lain.get((i + q) % lain.size());
                }
        }
        return out;
    }

    /**
     * Merges two arrays of blocks to add to what is known.
     * @param blocksA 
     * @param blocksB
     * @return array with known values merged
     * Prints errors if the arrays are different lengths, or if
     * there is an impossibility (an element marked as empty in one array and 
     * filled in the other).
     * -1, empty. 1, filled. Other values, known.
     */
    public static int[]  merge(int[] blocksA, int[] blocksB) throws UnsupportedOperationException {
        int l = blocksA.length;
        if (l != blocksB.length) {
            throw new UnsupportedOperationException("error in merge: different array lengths " + l
                    + " " + blocksB.length);
        }
        int[] result = new int[l];
        int a, b, out = 0;

        for (int i = 0; i < l; i++) {
            a = blocksA[i];
            b = blocksB[i];
            out=0;
            if(a == b){
                out=a;
            }
            else{
                if(a==0) out=b;
                else if(b==0) out=a;
                else if(a==empty&&b==filled||a==filled&&b==empty){
                new UnknownError("Error at element index " + i +
                            ": Impossible valeus ("+empty+" and "+filled+") found." +
                            " Setting out to zero.");
                }
                else
                    new UnknownError(" error at "+i);
            }
            result[i] = out;
        }

        return result;
    }

    /**
     * It merges the two arrays that you give it and if it changes something, it
     * creates a new event
     * @param blocksA an array you want to merge
     * @param blocksB an array you want to merge
     * @param EH the same EventHorrizon that is used everywhere else
     * @param XY the position
     * @param isHorizontal if it is horrizontal or not
     * @return the merged array
     */
    public static int[] superMerge(int[] blocksA, int[] blocksB,EventHorizon EH,int XY,boolean isHorizontal) {
        int l = blocksA.length;
        if (l != blocksB.length) {
            new UnsupportedOperationException("error in merge: different array lengths " + l
                    + " " + blocksB.length);
            return new int[0];
        }
        int[] result = new int[l];
        int a, b, out = 0;

        for (int i = 0; i < l; i++) {
            a = blocksA[i];
            b = blocksB[i];
            out=0;
            if(a == b){
                out=a;
                if(isHorizontal)
                    EH.Event(XY, i, a);
                else
                    EH.Event(i, XY, a);
            }
            else{
                if(a==0){
                    out=b;
                    if(isHorizontal)
                        EH.Event(XY, i, b);
                    else
                        EH.Event(i, XY, b);
                }
                else if(b==0){ out=a;}
                else if(a==empty&&b==filled||a==filled&&b==empty){
                new UnknownError("Error at element index " + i +
                            ": Impossible valeus ("+empty+" and "+filled+") found." +
                            " Setting out to zero.");
                }
                else
                    new UnknownError(" error at "+i);
            }
            result[i] = out;
        }

        return result;
    }

        /**
     * You are giving it two 2D integer arrays.  It checks to see if the two
     * arrays have equal lengths.  If they do, the method will add the integers
     * of each array at each index and makes that sum the index of a temperary
     * array.  It then sets the value of the of the starting arrays to whatever
     * the temperary array is.  If the two given arrays are not of equal lengths
     * it will throw the UnsupportedOperationException out and if it is not
     * caught it will give an error message.
         * @param alpha
         * @param beta
     */
    public static void merge(int[][] alpha,int[][] beta){
        if(alpha.length==beta.length){
            for(int i=0;i<alpha.length;i++){
                int[] temp=merge(alpha[i],beta[i]);
                alpha[i]=temp;
                beta[i]=temp;
            }
        }
                    new UnsupportedOperationException("error in merge: different array lengths ");
    }

        /**
         *
         * @param in
         * @param size
         * @return takes in an array and outputs the bianary string that
         * corisponds to the location of 0's and 1's
         */
    public static int[] permset(int[] in,int size){
        
        int ones=in.length;
        int zeros=Math.min(size-ones-sum(in)+1,0);
        int[] nums=new int[ones+zeros];
        
        for(int i=0;i<ones;i++){
            nums[i]=1;
        }
        for(int i=0;i<zeros;i++){
            nums[ones+i]=0;
        }
        return nums;
    }

    /**
     *Checks the set to see if it needs the permutations then it checks them
     * against something it knows and if it does not work, does not add them and
     * just returns the set it does know
     * @param knowen , an array you know
     * @param rule , the rule for that set
     * @return the set after it is filtered
     */
    public static ArrayList<boolean[]> filteredSet(int[] knowen,int[] rule){
        ArrayList<boolean[]> out=new ArrayList<boolean[]>();


        int[] nums=permset(rule,knowen.length);
        
         if(nums.length==1){
            out.add(convert(nums));
            return out;
        }
        for(int i=0;i<nums.length;i++){
        int[] temp=new int[knowen.length];
        temp[0] = nums[i / nums.length];

        ArrayList<Integer> lain = new ArrayList<Integer>();

        for (int yyz : nums) {
            
                lain.add(yyz);
           
        }
        for (int q = 1; q < knowen.length; q++) {
            temp[q] = lain.get((i + q) % lain.size());
            }

        try{
            merge(knowen,temp);
            out.add(convert(temp));
        }catch(UnknownError e){

        }

        }

        return out;
    }

/**
     * Checks if there is a difference
     * between the two lists.
     * @param oldList
     * @param newList
     * @return true if there is a difference.
     */
    public static boolean difference(int[] oldList, int[] newList) {
        int len = oldList.length;
        if (len != newList.length) {
            System.out.print("Error in changed, different list lengths");
        }
        for (int i = 0; i < len; i++) {
            if (oldList[i] != newList[i]) {
                return true;
            }
        }
        return false;
    }

    
    /**
     * Returns true if a boolean block of filled / empty squares
     * meets the filter (BaseCase.empty to force false, BaseCase.filled
     * to force true, all other values are wildcards).
     * @param squares
     * @param known
     * @return
     */
    public static boolean filter(boolean[] squares, int[] known) {
        int len = squares.length;
        if (known.length != len) {
            System.out.println("Error in filter, different array lengths");
            return false;
        }
        for (int i = 0; i < len; i++) {
            if(squares[i] && known[i] == empty) return false;
            else if (!squares[i] && known[i] == filled) return false;
        }
        return true;
    }

    /**
     *
     * @param lines Lines to be filtered
     * @param filter Filter to apply
     */
    public static void filterLines(ArrayList<boolean[]> lines, int[] filter) {
        int l = filter.length;
        if (lines == null || lines.isEmpty())  return;
        if (lines.get(0).length != l) {
            System.out.println("Error in filterLines: Line and filter " +
                    "length missmatch");
            return;
        }

        for (int i = 0; i < lines.size(); i++) {
            if (!filter(lines.get(i), filter)) {
                lines.remove(i);
                i--;
            }
        }

        if (lines.isEmpty()) {
            System.out.println("Error in filterLines: no remaining" +
                    "  permutation in list");
        }
    }
    
    /**
     * Assembles the boolean array of filled and empty squares
     * @param shifts The number of spaces block N is shifted by
     * @param result
     * @param blocks The length of block N
     * @return
     */
    public static boolean[] build(int[] shifts, boolean[] result,
                                   int[] blocks) {
        int j = 0;
        int numBlocks = blocks.length;
        for (int i = 0; i < numBlocks; i++) {
            for (int k = 0; k < shifts[i]; k++) {
                result[j] = false;
                j++;
            }
            if (i > 0) {
                result[j] = false;
                j++;
            }
            for (int k = 0; k < blocks[i]; k++) {
                result[j] = true;
                j++;
            }
        }
        return result;
    }



    /**
    * Calculates n!/d!. Useful for avoiding overflow when
     * dealing with large factorials -
    * a factorial of 21 overflows an unsigned long.
    * @param n Numerator factorial
    * @param d Denominator factorial
    * @return n!/d!
    */
    public static long factorialFraction(long n, long d) {
        if (n < 0 || d < 0 || d > n) return -1; // Error case
        if (n == 0) return 0;
        if (d == 0) return bang((int) n);
        if (d+1 == n) return n;
        if (d==n) return 1;
        long x = 1;
        for (long i = n+1; i <= d; i++) {
            x *= i;
        }
        return x;

    }


    /**
     *It creates a new integer, out, and sets it equal to 0.  It then runs
     * through every integer in the given integer arraylist and if the ineger is
     * greater than what is set for the integer set in out, it replaces the
     * integer set in out.  It does this for every integer in the given array to
     * find the largest number in the array and then returns that number.
     * @param in
     * @return the largest number in the array you give it
     */
    public static int Max(int[] in){
        int out=0;
        for(int i:in)
            if(i>out)
                out=i;
        return out;
    }


    /**
     * Marks empty spaces for when all blocks have been filled.
     * @param blocks
     * @param known
     * @return The original array (known) with any possible changes made.
     */
    public static int[] fillEmptySpaces(int[] blocks, int[] known) {
        int len = known.length;
        if (sum(blocks) == countEqualTo(known, filled)) {
            int[] squares = new int[len];
            for (int i = 0; i < len; i++) {
                if (known[i] == filled) squares[i] = filled;
                else squares[i] = empty;
            }
            return squares;

        }
        else return known;

    }

    /**
     * It makes the temperary 2D Array the same size as the Array that you give
     * it.  It then gets flipped from vertical to horrizontal
     * @param in
     * @return the flipped grid or ruleset
     */
    public static int[][]  FilpFlop(int[][] in){

        int[][] out=new int[in[0].length][in.length];
        for(int i=0;i<in[0].length;i++){
            //out[i]=new int[in[i].length];
            for(int q=0;q<in.length;q++){
                out[i][q]=in[q][i];
            }
        }
        return out;

    }

    /**
     * Checks every item in the list that you give it to see if it is equal to
     * the item you are asking for which will normally be either 2 or -2.  If it
     * is equal it will increment the count and when the for loop finishes, it
     * will return the count, telling how many instances of the item are in the
     * list
     * @param list
     * @param item
     * @return number of instances of the item are in the list
     */
    public static  int countEqualTo(int[] list, int item) {
        int count = 0;
        for (int n : list) {
            if (n == item) count++;

        }
         return count;
}

//takes the rule and the 'string' and make the XXX's and spaces.
    /**
     *
     * @param in
     * @param rule
     * @param length
     * @return
     */
    public static boolean[] permutation(boolean[] in,int[] rule,int length){
        int zig=0, pos=0;
        boolean[] out=new boolean[length];
        for(int i=0;i<in.length;i++){
            
            if(in[i]){
                for(int r=0;r<rule[zig];r++){
                    out[pos]=true;
                    pos++;
                }
            zig++;
            }
            
        }
        return out;
    }

    /**
     * Finds what is true in both a and b, and returns the result.
     * Used for determinining what is true in all permutations
     * @param a
     * @param b
     * @return
     */
    public static int[] andMerge(int[] a, boolean[] b) {
        int len = a.length;
        int[] out = new int[len];
        
        for (int i = 0; i < len; i++) {
            if (a[i] == filled && b[i]) out[i] = filled;
            else if (a[i] == empty && !b[i]) out[i] = empty;
            else out[i] = 0;
        }
        return out;
    }

    /**
     * Finds what is known based on all permutations. <br />
     * Returns zero for a square if nothing definite is known about it, the
     * value of filled for filled in all perms, and the value of empty for
     * empty in all perms.
     * @param perms 
     * @return
     */
    public static int[] knownInAll(Perms perms) {
        int len = perms.size();
        int[] out = new int[len];
        
        for (int i = 0; i < len; i++) {
            out[i] = 0;
        }
        for (int i = 0; i < len; i++) {
            out = andMerge(out, convert(perms.get(i)));
        }
        return out;
    }

    /**
     * It creates a new 2D boolean array and makes it the length of the 2D
     * integer array you just gave it.  It runs through every index of the array
     * you give it and it checks at each index to see if that index has the same
     * value as the filled to see if the block is shaded.  If the values are
     * equal, it sets the boolean array at that index to true.  It then returns
     * that boolean array.
     * @param in
     * @return a boolean array telling which of the integer arrays blocks are
     * filled
     */
    public static boolean[][] convert(int[][] in){
        boolean[][] out=new boolean[in.length][in[0].length];
        for(int i=0;i<out.length;i++)
            out[i]=convert(in[i]);
        return out;
    }


    /**
     * It creates a local 2D integer array with the length of the 2D boolean
     * array you give it.  It then goes through each index in the boolean array
     * and if the value is true, it sets the interger array's index to filled
     * which is 2, and if the boolean index is false it sets the integer array's
     * index to empty which is -2.  It then returns the integer array.
     * @param in
     * @return a integer array that has values that are filled or empty
     * depending on the boolean array you give it
     */
    public static int[][] convert(boolean[][] in){
        int[][] out=new int[in.length][in[0].length];
        for(int i=0;i<out.length;i++)
            out[i]=convert(in[i]);
        return out;
    }
    public static int[][] convert(ArrayList<boolean[]> in){
        boolean[][] out=new boolean[in.size()][];
        for(int i=0;i<out.length;i++){
            out[i]=in.get(i);
        }
        
        return convert(out);
    }
    /**
     * It creates a new boolean array and makes it the length of the integer
     * array you just gave it.  It runs through every index of the array you
     * give it and it checks at each index to see if that index has the same
     * value as the filled to see if the block is shaded.  If the values are
     * equal, it sets the boolean array at that index to true.  It then returns
     * that boolean array.
     * @param in
     * @return a boolean array telling which of the integer arrays blocks are
     * filled
     */
    public static boolean[] convert(int[] in){
        boolean[] out=new boolean[in.length];
        for(int i=0;i<in.length;i++){
            out[i]=in[i]==filled;
        }
        
        return out;
    }

    /**
     * It creates a local integer array with the length of the boolean array you
     * give it.  It then goes through each index in the boolean array and if the
     * value is true, it sets the interger array's index to filled which is 2,
     * and if the boolean index is false it sets the integer array's index to
     * empty which is -2.  It then returns the integer array.
     * @param in
     * @return a integer array that has values that are filled or empty
     * depending on the boolean array you give it
     */
    public static int[] convert(boolean[] in){
        int[] out=new int[in.length];
        for(int i=0;i<in.length;i++){
            if(in[i])
                out[i]=filled;
            else
                out[i]=empty;
        }
        return out;
    }




    /**
     * Finds squares filled in all permutations.
     * @param blocks
     * @param length
     * @return  Array with values known marked as 1, unknown as 0.
     */
    public static int[] simpleBoxes(int[] blocks, int length) {
        int count = blocks.length;
        int[] result = new int[length];
        int rightSide, leftSide;
        for (int i = 0; i < length; i++) result[i] = 0;

        for (int i = 0; i < count; i++) {
            // Compute borders of left-most and right-most positions
            rightSide = blocks[i];
            leftSide = length - blocks[i];

            for (int j = 0; j < i; j++) {
                rightSide += 1 + blocks[j];
            }
            for (int j = i + 1; j < count; j++) {
                leftSide -= 1 + blocks[j];
            }

            // fill in squares between
            for (int j = leftSide; j < rightSide; j++) {
                result[j] = filled;
            }
        }

        return result;
    }

}
